// 导入优先队列库（小顶堆）
import TinyQueue from 'tinyqueue';

// 地球半径（单位：公里）
const earthRadius = 6371;
// 角度到弧度的转换常数
const rad = Math.PI / 180;

/**
 * 查找指定坐标附近的最近邻点
 * @param {Object} index - kd-tree索引对象，包含ids、coords、nodeSize等属性
 * @param {number} lng - 查询点的经度
 * @param {number} lat - 查询点的纬度
 * @param {number} maxResults - 返回的最大结果数量（默认无限制）
 * @param {number} maxDistance - 搜索的最大距离，单位公里（默认无限制）
 * @param {Function} predicate - 可选的过滤函数，用于过滤结果
 * @returns {Array} 返回符合条件的点ID数组
 */
export function around(
  index,
  lng: number,
  lat: number,
  maxResults: number = Infinity,
  maxDistance: number = Infinity,
  predicate?: (val: number) => boolean
) {
  let maxHaverSinDist = 1; // 最大haversine距离阈值
  const result: any = []; // 存储搜索结果

  // 设置默认值
  if (maxResults === undefined) maxResults = Infinity;
  if (maxDistance !== undefined) maxHaverSinDist = haverSin(maxDistance / earthRadius);

  // 创建一个距离排序的优先队列（小顶堆），同时存储点和kd-tree节点
  const q = new TinyQueue([], compareDist);

  // 创建根节点对象，代表整个地球（整个kd-tree的顶部）
  let node = {
    left: 0, // kd-tree数组中的左索引
    right: index.ids.length - 1, // kd-tree数组中的右索引
    axis: 0, // 分割轴：0表示经度轴，1表示纬度轴
    dist: 0, // 存储子节点到查询点距离的下界
    minLng: -180, // 节点的包围盒（边界框）
    minLat: -90,
    maxLng: 180,
    maxLat: 90
  };

  // 预计算查询点纬度的余弦值，用于加速距离计算
  const cosLat = Math.cos(lat * rad);

  while (node) {
    const right = node.right;
    const left = node.left;

    // 如果是叶子节点（节点规模小于等于nodeSize）
    if (right - left <= index.nodeSize) {
      // 将叶子节点中的所有点添加到队列中
      for (let i = left; i <= right; i++) {
        const id = index.ids[i];
        // 如果没有提供过滤函数，或者点通过了过滤
        if (!predicate || predicate(id)) {
          // 计算该点到查询点的haversine距离
          const dist = haverSinDist(lng, lat, index.coords[2 * i], index.coords[2 * i + 1], cosLat);
          q.push({ id, dist }); // 将点和距离一起加入队列
        }
      }
    } else {
      // 不是叶子节点（有子节点）

      // 计算中间索引（右移操作相当于除以2并向下取整）
      const m = (left + right) >> 1;
      // 获取中间点的经纬度
      const midLng = index.coords[2 * m];
      const midLat = index.coords[2 * m + 1];

      // 将中间点添加到队列中
      const id = index.ids[m];
      if (!predicate || predicate(id)) {
        const dist = haverSinDist(lng, lat, midLng, midLat, cosLat);
        q.push({ id, dist });
      }

      // 计算下一个分割轴（在经度0和纬度1之间切换）
      const nextAxis = (node.axis + 1) % 2;

      // 创建左子节点（节点的前半部分）
      const leftNode = {
        left,
        right: m - 1,
        axis: nextAxis,
        minLng: node.minLng,
        minLat: node.minLat,
        // 如果在经度轴上分割，更新最大经度；否则保持原值
        maxLng: node.axis === 0 ? midLng : node.maxLng,
        // 如果在纬度轴上分割，更新最大纬度；否则保持原值
        maxLat: node.axis === 1 ? midLat : node.maxLat,
        dist: 0
      };
      // 创建右子节点（节点的后半部分）
      const rightNode = {
        left: m + 1,
        right,
        axis: nextAxis,
        // 如果在经度轴上分割，更新最小经度；否则保持原值
        minLng: node.axis === 0 ? midLng : node.minLng,
        // 如果在纬度轴上分割，更新最小纬度；否则保持原值
        minLat: node.axis === 1 ? midLat : node.minLat,
        maxLng: node.maxLng,
        maxLat: node.maxLat,
        dist: 0
      };

      // 计算左子节点到查询点的距离下界
      leftNode.dist = boxDist(lng, lat, cosLat, leftNode);
      // 计算右子节点到查询点的距离下界
      rightNode.dist = boxDist(lng, lat, cosLat, rightNode);

      // 将左右子节点都添加到队列中
      q.push(leftNode);
      q.push(rightNode);
    }

    // 从队列中取出最近的候选点
    // 这些点保证比其他未处理点（包括kd-tree节点中的点）更近，
    // 因为每个节点的距离都是其子节点距离的下界
    while (q.length && q.peek().id != null) {
      const candidate = q.pop();
      // 如果候选点距离超出最大阈值，返回结果
      if (candidate.dist > maxHaverSinDist) return result;
      result.push(candidate.id);
      // 如果结果数量达到上限，返回结果
      if (result.length === maxResults) return result;
    }

    // 取出下一个最近的kd-tree节点继续处理
    node = q.pop();
  }

  return result;
}

/**
 * 计算从一个位置点到包围盒内所有点距离的下界
 * 用于剪枝：如果包围盒的距离下界都比最大距离大，可以跳过整个包围盒
 */
function boxDist(lng, lat, cosLat, node) {
  const minLng = node.minLng;
  const maxLng = node.maxLng;
  const minLat = node.minLat;
  const maxLat = node.maxLat;

  // 如果查询点在最小和最大经度之间
  if (lng >= minLng && lng <= maxLng) {
    // 如果查询点在包围盒下方
    if (lat < minLat) return haverSin((lat - minLat) * rad);
    // 如果查询点在包围盒上方
    if (lat > maxLat) return haverSin((lat - maxLat) * rad);
    // 查询点在包围盒内部，距离下界为0
    return 0;
  }

  // 如果查询点在包围盒的东西两侧
  // 计算从查询点到最近经度的极值点（纬度方向上距离最短的点）
  const haverSinDLng = Math.min(haverSin((lng - minLng) * rad), haverSin((lng - maxLng) * rad));
  const extremumLat = vertexLat(lat, haverSinDLng);

  // 如果极值点在包围盒内，返回到极值点的距离
  if (extremumLat > minLat && extremumLat < maxLat) {
    return haverSinDistPartial(haverSinDLng, cosLat, lat, extremumLat);
  }
  // 否则返回到包围盒某个角点的距离（取最近的角点）
  return Math.min(
    haverSinDistPartial(haverSinDLng, cosLat, lat, minLat),
    haverSinDistPartial(haverSinDLng, cosLat, lat, maxLat)
  );
}

/**
 * 比较函数：用于优先队列排序，按距离从小到大
 */
function compareDist(a, b) {
  return a.dist - b.dist;
}

/**
 * Haversine公式：计算角度的haversine值
 * haversine(θ) = sin²(θ/2)
 */
function haverSin(theta) {
  const s = Math.sin(theta / 2);
  return s * s;
}

/**
 * Haversine距离的部分计算
 * 用于计算球面上两点之间的距离
 */
function haverSinDistPartial(haverSinDLng, cosLat1, lat1, lat2) {
  return cosLat1 * Math.cos(lat2 * rad) * haverSinDLng + haverSin((lat1 - lat2) * rad);
}

/**
 * 计算球面上两点之间的haversine距离
 * @param {number} lng1 - 第一点经度
 * @param {number} lat1 - 第一点纬度
 * @param {number} lng2 - 第二点经度
 * @param {number} lat2 - 第二点纬度
 * @param {number} cosLat1 - 第一点纬度的余弦值（预计算）
 * @returns {number} haversine距离
 */
function haverSinDist(lng1, lat1, lng2, lat2, cosLat1) {
  const haverSinDLng = haverSin((lng1 - lng2) * rad);
  return haverSinDistPartial(haverSinDLng, cosLat1, lat1, lat2);
}

/**
 * 计算地球表面上两点间的实际距离（单位：公里）
 * @param {number} lng1 - 第一点经度
 * @param {number} lat1 - 第一点纬度
 * @param {number} lng2 - 第二点经度
 * @param {number} lat2 - 第二点纬度
 * @returns {number} 两点间的距离（公里）
 */
export function distance(lng1, lat1, lng2, lat2) {
  const h = haverSinDist(lng1, lat1, lng2, lat2, Math.cos(lat1 * rad));
  // 将haversine值转换为实际距离：d = 2R * arcsin(√h)
  return 2 * earthRadius * Math.asin(Math.sqrt(h));
}

/**
 * 计算极值纬度：在给定经度差的情况下，使球面距离最短的纬度值
 * 用于boxDist函数中计算包围盒距离下界
 */
function vertexLat(lat, haverSinDLng) {
  const cosDLng = 1 - 2 * haverSinDLng;
  // 特殊情况：当cosDLng <= 0时，极值点在极点
  if (cosDLng <= 0) return lat > 0 ? 90 : -90;
  // 计算使距离最短的纬度值
  return Math.atan(Math.tan(lat * rad) / cosDLng) / rad;
}
